﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringDefs.Bioinformatics
{
    public static  class Bioinformatics
    {
        /// <summary>
        /// Creates a score matrix that will be used in LongestCommonSubsequnce method
        /// </summary>
        /// <param name="x">First String</param>
        /// <param name="y">Second String</param>
        /// <returns></returns>
        private static int[,] CreateLCSMatrix(string x, string y)
        {


            int m = x.Length;
            int n = y.Length;
            int[,] T = new int[m, n];
            for (int i = 0; i < m; i++)
                T[i, 0] = 0;
            for (int i = 0; i < n; i++)
                T[0, i] = 0;
            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    if (x[i] == y[j])
                        T[i, j] = T[i - 1, j - 1] + 1;
                    else
                        T[i, j] = Math.Max(T[i, j - 1], T[i - 1, j]);
                }
            }
            return T;

        }
        /// <summary>
        /// Finds the longest commong sub-sequence of two Strings
        /// </summary>
        /// <param name="x">The first string</param>
        /// <param name="y">The second string</param>
        /// <returns></returns>
        /// <remarks>If you want to know about the logic,I recommend the following link
        /// http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node4.html
        /// Prof. Lecroq has several other string processing document 
        /// those are quite interesting and amazing read. 
        /// </remarks>
        public static string LongestCommonSubsequence(this string x, string y)
        {

            List<char> lcs = new List<char>();
            StringBuilder sb = new StringBuilder();

            x = " " + x;
            y = " " + y;
            int[,] T = CreateLCSMatrix(x, y);

            int m = x.Length;
            int n = y.Length;
            int i = m - 1;
            int j = n - 1;
            //int k = T[m - 1, n - 1] - 1;
            while (i > 0 && j > 0)
            {
                if (T[i, j] == T[i - 1, j - 1] + 1 && x[i] == y[j])
                {
                    lcs.Add(x[i]);

                    i--;
                    j--;
                    //      k--;
                }
                else if (T[i - 1, j] > T[i, j - 1])
                {
                    i--;
                }
                else
                    j--;
            }

            for (int p = lcs.Count - 1; p >= 0; p--)
            {
                sb.Append(lcs[p].ToString());
            }

            return sb.ToString();
        }
        /// <summary>
        /// This method returns longest common subsequence ration. 
        /// </summary>
        /// <param name="x">First String</param>
        /// <param name="y">Second String</param>
        /// <param name="lcs">Longest Common Subsequence</param>
        /// <returns>a value that gives a measurement of the proximity of the two strings</returns>
        public static double LCSR(this string x, string y, string lcs)
        {
            double r = (double)lcs.Length / (double)Math.Max(x.Length, y.Length);
            return r < 1 ? r : 1;

        }

       
        /// <summary>
        /// Returns the length of the Longest Common Subsequence for two strings
        /// </summary>
        /// <param name="str1">This is the first string</param>
        /// <param name="str2">This is the second string</param>
        /// <returns>Returns the length of the longest common subsequnce without actually calculating the Longest Common Subsequence</returns>
        /// <remarks>This source is from http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring</remarks>
        public static  int LCSLength(this string str1, string str2)
        {
            if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
                return 0;

            int[,] num = new int[str1.Length, str2.Length];
            int maxlen = 0;

            for (int i = 0; i < str1.Length; i++)
            {
                for (int j = 0; j < str2.Length; j++)
                {
                    if (str1[i] != str2[j])
                        num[i, j] = 0;
                    else
                    {
                        if ((i == 0) || (j == 0))
                            num[i, j] = 1;
                        else
                            num[i, j] = 1 + num[i - 1, j - 1];

                        if (num[i, j] > maxlen)
                        {
                            maxlen = num[i, j];
                        }
                    }
                }
            }
            return maxlen;
        }
        /// <summary>
        /// This method finds the Longest Common Sub-String of two strings
        /// </summary>
        /// <param name="str1">First String</param>
        /// <param name="str2">Secong String</param>
        /// <returns></returns>
        /// <remarks>This source is from http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring</remarks>
        public static string LongestCommonSubstring(this string str1, string str2)
        {
            string sequence = string.Empty;
            if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
                return string.Empty;

            int[,] num = new int[str1.Length, str2.Length];
            int maxlen = 0;
            int lastSubsBegin = 0;
            StringBuilder sequenceBuilder = new StringBuilder();

            for (int i = 0; i < str1.Length; i++)
            {
                for (int j = 0; j < str2.Length; j++)
                {
                    if (str1[i] != str2[j])
                        num[i, j] = 0;
                    else
                    {
                        if ((i == 0) || (j == 0))
                            num[i, j] = 1;
                        else
                            num[i, j] = 1 + num[i - 1, j - 1];

                        if (num[i, j] > maxlen)
                        {
                            maxlen = num[i, j];
                            int thisSubsBegin = i - num[i, j] + 1;
                            if (lastSubsBegin == thisSubsBegin)
                            {//if the current LCS is the same as the last time this block ran
                                sequenceBuilder.Append(str1[i]);
                            }
                            else //this block resets the string builder if a different LCS is found
                            {
                                lastSubsBegin = thisSubsBegin;
                                sequenceBuilder.Remove(0, sequenceBuilder.Length);//clear it
                                sequenceBuilder.Append(str1.Substring(lastSubsBegin, (i + 1) - lastSubsBegin));
                            }
                        }
                    }
                }
            }
            sequence = sequenceBuilder.ToString();
            return sequence;
        }
    }
}
